package com.berchen.数据结构.二叉树.赫夫曼编解码;

import java.io.*;
import java.util.*;

/**
 * 赫夫曼编码解码
 * 编码
 * 1、将字符串变成List<HuffmanNode>
 * 2、将List变成赫夫曼树
 */
public class HuffmanCode {

    // 存放赫夫曼编码表 a=110 等形式的
    private static Map<Byte, String> huffmanCode = new HashMap<>();
    // 用来拼接路径  存储某个叶子节点的路径
    private static StringBuilder stringBuilder = new StringBuilder();

    public static void main(String[] args) {

//        String str = "i like like like java do you like a java java";
        String str = "aaaaaaaaa 000000 0a0a00a0000 00 0000 java i like like 0   ";
        byte[] zip = zip(str);
        System.out.println(Arrays.toString(zip));
        byte[] bytes = unZip(huffmanCode, zip);
        System.out.println(new String(bytes));
//        String srcFile="E:\\1project\\test-util\\src\\main\\java\\com\\berchen\\数据结构\\二叉树\\赫夫曼编解码\\yuan.jpg";
//        String sdtFile="E:\\1project\\test-util\\src\\main\\java\\com\\berchen\\数据结构\\二叉树\\赫夫曼编解码\\mudi.zip";
//        zipFile(srcFile,sdtFile);
//        System.out.println("压缩文件成功");
//        unZipFile(sdtFile,"E:\\1project\\test-util\\src\\main\\java\\com\\berchen\\数据结构\\二叉树\\赫夫曼编解码\\mudi.jpg");

    }

    /**
     * 解压文件
     * @param zipFile
     * @param sdtFile
     */
    public static void unZipFile(String zipFile,String sdtFile){

        InputStream is=null;
        ObjectInputStream ois=null;
        OutputStream os=null;

        try{

            is=new FileInputStream( zipFile);
            ois=new ObjectInputStream(is);

            // 得到压缩后的数据
            byte[] huffmanByte= (byte[]) ois.readObject();

            // 得到赫夫曼树编码
            Map<Byte,String> huffmanCode= (Map<Byte, String>) ois.readObject();

            byte[] bytes = unZip(huffmanCode, huffmanByte);
            os=new FileOutputStream(sdtFile);
            os.write(bytes);    // 写到目标文件


        }catch (Exception e){
            e.printStackTrace();
        }finally {
            try{
                os.close();
                ois.close();
                is.close();
            }catch (Exception e){
                e.printStackTrace();
            }
        }
    }

    /**
     * 将源文件压缩  到目标路径
     * @param srcFile 源文件路径
     * @param sdtFile 目标路径
     */
    public static void zipFile(String srcFile,String sdtFile){

        InputStream is=null;
        OutputStream os=null;
        ObjectOutputStream oos=null;
        try{

            // 读取源文件
            is=new FileInputStream(srcFile);
            byte b[]=new byte[is.available()];
            is.read(b);

            // 压缩
            byte[] huffmanByte = zip(b);    // 得到压缩后的数据

            os=new FileOutputStream(sdtFile);
            oos=new ObjectOutputStream(os);
            // 将压缩后的数据写入新文件
            oos.writeObject(huffmanByte);
            // 将赫夫曼编码 写入新文件 解压才能完成
            oos.writeObject(huffmanCode);

        }catch (Exception e){
            e.printStackTrace();
        }
        finally {
            try{
                is.close();
                oos.close();
                os.close();
            }catch (Exception e){e.printStackTrace();}
        }
    }

    /**
     * 将压缩后的byte 解压缩
     * @param map           赫夫曼编码的map
     * @param huffmanByte   压缩后的byte
     * @return
     */
//    public static byte[] unZip(Map<Byte,String> map,byte[] huffmanByte){
//
//        // 将压缩后的byte 变成 字符串 101001101001001
//        StringBuilder sb=new StringBuilder();
//        for(int i =0;i<huffmanByte.length;i++){
//            sb.append(byteToBitString(!(i==huffmanByte.length-1),huffmanByte[i]));
//        }
//
//        // 将 Map的key和value 互换
//        Map<String,Byte> byteMap=new HashMap<>();
//        for(Map.Entry<Byte,String> entry:map.entrySet()){
//            byteMap.put(entry.getValue(),entry.getKey());
//        }
//
//        // 循环读取 sb  进行匹配 byteMap
//        List<Byte> byteList=new ArrayList<>();
//        for(int i =0;i<sb.length();){
//            boolean falg=true;
//            int count=1;
//            Byte b=null;
//
//            while (falg){
//                String str=sb.substring(i,i+count);
//                b = byteMap.get(str);
//                if(b==null){
//                    count++;
//                }
//                else {
//                    falg=false;
//                }
//            }
//            byteList.add(b);
//            i+=count;
//        }
//
//        byte[] b=new byte[byteList.size()];
//        for(int i =0;i<byteList.size();i++){
//            b[i]=byteList.get(i);
//        }
//
//        return b;
//    }
    private static byte[] unZip(Map<Byte,String> mapCode,byte[] byteCode){

        // 1、 先得到赫夫曼编码得到的字节数组转成的二进制的字符串
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<byteCode.length;i++){

            boolean flag=!(i==byteCode.length-1);  // 如果是最后一个，就不需要补高位，就设置为false
            sb.append(byteToBitString(flag,byteCode[i]));
        }

        // 2、 将字符串按照 执行的赫夫曼编码进行解码
        // 将赫夫曼编码表调转（key与value互换），因为要反向查
        Map<String,Byte> mapDeCode=new HashMap<>();
        for(Map.Entry<Byte,String> m:mapCode.entrySet()){

            mapDeCode.put(m.getValue(),m.getKey());
        }

        // 创建一个集合，存放byte
        // 将反编码表 与数据进行匹配 解码
        List<Byte> list=new ArrayList<>();
        StringBuilder sb2=new StringBuilder();
        for(int i=0;i<sb.length();i++){

            sb2.append(sb.substring(i,i+1));    // 取出一个，并且添加到缓冲区中
            Byte b = mapDeCode.get(sb2.toString());
            if(b==null) // 没有匹配的
                continue;
            else {    // 有匹配的
                list.add(b);
                sb2.delete(0,sb2.length()); // 清空缓冲区
            }
        }
        // for循环结束后，list中就存放了所有的字符i like like like java do you like a java

        // 吧list中的数据放入到byte数组中并返回
        byte[] b=new byte[list.size()];
        for(int i=0;i<b.length;i++){

            b[i]=list.get(i);
        }
        return b;
    }

    /**
     * 将一个byte转成一个二进制的字符串。
     *
     * @param flag 是否需要补高位 true 需要  false 不需要
     * @param b    传入的byte
     * @return 该byte对应的二进制的字符串 注意是补码返回的。
     */
    private static String byteToBitString(boolean flag, byte b) {

        int temp = b; // 将b转成 int
        if (flag) {
            temp |= 256;  // 按位与  256= 1 0000 0000    | 1=0000 0001 =》10000 0001
        }
        String str = Integer.toBinaryString(temp);    // 返回的是temp对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }

    /**
     * 封装操作
     *
     * @param str 需要进行压缩的数据
     * @return 返回的是经过赫夫曼编码处理后的字节数组
     */
    public static byte[] zip(String str) {
        return zip(str.getBytes());
    }
    public static byte[] zip(byte[] bytes){
        getHuffmanMap(createHuffman(getListByStr(bytes)));
        return zip(bytes, huffmanCode);
    }

    /**
     * 编码 将bytes 进行编码
     *
     * @param bytes
     * @return 编码后的字节数组 即8位对应一个byte 放入一个byte数组中
     * 10101000 （补码） -》 byte (推导： 10101000 -1 => 10100111（反码）=>11011000（原码）=>-88 )
     */
    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCode) {

        // huffmanCode 将 bytes转成赫夫曼编码对应的字符串 010010101010100101010010
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < bytes.length; i++) {
            result.append(huffmanCode.get(bytes[i]));
        }

        System.out.println(result.length());
        // 存储压缩后的byte数组
        byte[] resultByte = new byte[(result.length() + 7) / 8]; // 这个效果和下面是一样的
//        byte[] resultByte=new byte[result.length()%8==0?result.length():result.length()+1];

        int index = 0;
        String strByte;
        for (int i = 0; i < result.length(); i += 8) {    // 因为每8位一个 byte，所以步长为8
            if (i + 8 <= result.length()) {
                strByte = result.substring(i, i + 8);
            } else {    // 不够8位置
                strByte = result.substring(i);
            }
            // 将strByte 转成byte 放入resultByte中
            resultByte[index++] = (byte) Integer.parseInt(strByte, 2); // 将str转成byte
        }

        return resultByte;
    }

    /**
     * 调用这个方法
     *
     * @param root
     */
    public static void getHuffmanMap(HuffmanNode root) {
        if (root == null) {
            return;
        }
        getHuffmanMap(root, "", stringBuilder);
    }

    /**
     * 将赫夫曼树变成 map编码表
     * 将传入的node的结点的所有叶子结点的赫夫曼编码得到，并放入到huffmanCode集合中
     *
     * @param node
     * @param code 路径值
     * @param sb   前路径的值
     */
    public static void getHuffmanMap(HuffmanNode node, String code, StringBuilder sb) {

        StringBuilder stringBuilder1 = new StringBuilder(sb);
        stringBuilder1.append(code);    // 拼接这一层的路径
        if (node != null) {

            // 判断是否是叶子节点
            if (node.date == null) {    // 不是叶子节点
                getHuffmanMap(node.left, "0", stringBuilder1);
                getHuffmanMap(node.right, "1", stringBuilder1);
            } else {
                // 是叶子节点
                huffmanCode.put(node.date, stringBuilder1.toString());
            }
        }
    }


    /**
     * 创建一个赫夫曼树
     *
     * @param nodes
     * @return
     */
    public static HuffmanNode createHuffman(List<HuffmanNode> nodes) {
        while (nodes.size() >= 2) {
            Collections.sort(nodes);
            HuffmanNode leftNode = nodes.get(0);
            HuffmanNode rightNode = nodes.get(1);
            HuffmanNode root = new HuffmanNode(null, leftNode.weight + rightNode.weight);
            root.left = leftNode;
            root.right = rightNode;
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(root);
        }
        return nodes.get(0);
    }
    public static List<HuffmanNode> getListByStr(byte[] bytes){
        Map<Byte, Integer> counts = new HashMap<>();
        // 得到字符在字符串中出现的次数
        for (int i = 0; i < bytes.length; i++) {
            Integer count = counts.get(bytes[i]);
            if (count == null) {
                counts.put(bytes[i], 1);
            } else {
                counts.put(bytes[i], count + 1);
            }
        }
        // 创建List
        List<HuffmanNode> nodes = new ArrayList<>();
        Set<Map.Entry<Byte, Integer>> entries = counts.entrySet();
        for (Map.Entry<Byte, Integer> entry : entries) {
            nodes.add(new HuffmanNode(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    /**
     * 将字符串 构建成一个List
     *
     * @param str
     * @return
     */
    public static List<HuffmanNode> getListByStr(String str) {
        return getListByStr(str.getBytes());
    }

}
